/**
 * @file selection.c
 * @brief Genetic functions for selecting modules for reproduction
 * @author Scott Moyers
 * @date 2009
 */

#include "selection.h"
#include "util.h"

#include <float.h>
#include <string.h>

/** selection function pointer array to make selecting selection functions easy */
SelectionFunc selection_functions[SEL_FUNCS] = {
	fittest_selection,
	roulette_wheel_selection,
	tournament_selection,
	roulette_tournament_selection
};

SelectionFunc get_selection_func(const char *func)
{
	if (!strcmp(func, "fittest_selection")) {
		return &fittest_selection;
	} else if (!strcmp(func, "roulette_wheel_selection")) {
		return &roulette_wheel_selection;
	} else if (!strcmp(func, "tournament_selection")) {
		return &tournament_selection;
	} else if (!strcmp(func, "roulette_tournament_selection")) {
		return &roulette_tournament_selection;
	}
	return NULL;
}

/**
 * comparison function for module fitnesses
 * @param _a pointer to a module
 * @param _b pointer to a module
 * @retval -1 if a is fitter than b
 * @retval 0 if a's fitness is equal to b's fitness
 * @retval 1 if b is fitter than a
 */
static int compare_fitness(const void *_a, const void *_b)
{
	const float a = (*(const struct Module**) _a)->fitness;
	const float b = (*(const struct Module**) _b)->fitness;

	if(a > b) return -1;
	else {
		if(a == b) return 0;
		else       return 1;
	}
}

void fittest_selection(dsfmt_t *dsfmt, struct Module *m[], unsigned int n, unsigned int sel)
{
	(void) dsfmt; /* remove unused parameter warning */
	(void) sel;   /* remove unused parameter warning */
	/* sort so the fittest parents are at the start of the array */
	qsort(m, n, sizeof(m[0]), &compare_fitness);
}

void roulette_wheel_selection(dsfmt_t *dsfmt, struct Module *m[], unsigned int n, unsigned int sel)
{
	struct Module **tmp;
	unsigned int i;
	double *probs = (double *) smalloc(n * sizeof(double));
	double sum = 0.0;
	double min = DBL_MAX;
	double max = 0.0;

	for(i = 0; i < n; i++) {
		if (m[i]->fitness < min) {
			min = m[i]->fitness;
		}

		if (m[i]->fitness > max) {
			max = m[i]->fitness;
		}
	}

	/* adjust the range of fitnesses so it's [0, 1) */
	for(i = 0; i < n; i++) {
		probs[i] = (m[i]->fitness - min) / (max - min);
		sum += probs[i];
	}

	tmp = (struct Module **) smalloc(sizeof(struct Module *) * sel);
	for(i = 0; i < sel; i++) {
		unsigned int j;
		double acc = 0.0;
		double r = dsfmt_genrand_close_open(dsfmt) * sum;
		for(j = 0; acc <= r; j++) {
			acc += probs[j];
		}
		tmp[i] = copy_module(m[j - 1]);
	}

	for(i = 0; i < sel; i++) {
		free_module(m[i]);
		m[i] = tmp[i];
	}

	free(probs);
	free(tmp);
}

void tournament_selection(dsfmt_t *dsfmt, struct Module *m[], unsigned int n, unsigned int sel)
{
	unsigned int i;
	struct Module **tmp = (struct Module **) smalloc(sizeof(struct Module *) * sel);
	for(i = 0; i < sel; i++) {
		struct Module *m1 = m[(int) dsfmt_genrand_close_open(dsfmt) * n];
		struct Module *m2 = m[(int) dsfmt_genrand_close_open(dsfmt) * n];
		if (m1->fitness > m2->fitness) {
			tmp[i] = copy_module(m1);
		} else {
			tmp[i] = copy_module(m2);
		}
	}

	for(i = 0; i < sel; i++) {
		free_module(m[i]);
		m[i] = tmp[i];
	}
	free(tmp);
}

void roulette_tournament_selection(dsfmt_t *dsfmt, struct Module *m[], unsigned int n, unsigned int sel)
{
	struct Module **tmp;
	unsigned int i;
	double *probs = (double *) smalloc(n * sizeof(double));
	double sum = 0.0;
	double min = DBL_MAX;
	double max = 0.0;

	for(i = 0; i < n; i++) {
		if (m[i]->fitness < min) {
			min = m[i]->fitness;
		}

		if (m[i]->fitness > max) {
			max = m[i]->fitness;
		}
	}

	/* adjust the range of fitnesses so it's [0, 1) */
	for(i = 0; i < n; i++) {
		probs[i] = (m[i]->fitness - min) / (max - min);
		sum += probs[i];
	}

	tmp = (struct Module **) smalloc(sizeof(struct Module *) * sel);
	for(i = 0; i < sel; i++) {
		unsigned int k;
		struct Module *comp[2];
		for(k = 0; k < 2; k++) {
			unsigned int j;
			double acc = 0.0;
			double r = dsfmt_genrand_close_open(dsfmt) * sum;
			for(j = 0; acc <= r; j++) {
				acc += probs[j];
			}
			comp[k] = m[j - 1];
		}
		if (comp[0]->fitness > comp[1]->fitness) {
			tmp[i] = copy_module(comp[0]);
		} else {
			tmp[i] = copy_module(comp[1]);
		}
	}

	for(i = 0; i < sel; i++) {
		free_module(m[i]);
		m[i] = tmp[i];
	}

	free(probs);
	free(tmp);
}
